<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
           "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<title>Coverage Report</title>
<link title="Style" type="text/css" rel="stylesheet" href="css/main.css"/>
<script type="text/javascript" src="js/popup.js"></script>
</head>
<body>
<h5>Coverage Report - org.dellroad.stuff.graph.TopologicalSorter</h5>
<div class="separator">&nbsp;</div>
<table class="report">
<thead><tr>  <td class="heading">Classes in this File</td>  <td class="heading"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">Line Coverage</a></td>  <td class="heading"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">Branch Coverage</a></td>  <td class="heading"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">Complexity</a></td></tr></thead>
  <tr><td><a href="org.dellroad.stuff.graph.TopologicalSorter.html">TopologicalSorter</a></td><td><table cellpadding="0px" cellspacing="0px" class="percentgraph"><tr class="percentgraph"><td align="right" class="percentgraph" width="40">95%</td><td class="percentgraph"><div class="percentgraph"><div class="greenbar" style="width:95px"><span class="text">43/45</span></div></div></td></tr></table></td><td><table cellpadding="0px" cellspacing="0px" class="percentgraph"><tr class="percentgraph"><td align="right" class="percentgraph" width="40">100%</td><td class="percentgraph"><div class="percentgraph"><div class="greenbar" style="width:100px"><span class="text">16/16</span></div></div></td></tr></table></td><td class="value"><span class="hidden">2.2222222222222223;</span>2.222</td></tr>
  <tr><td><a href="org.dellroad.stuff.graph.TopologicalSorter.html">TopologicalSorter$1</a></td><td><table cellpadding="0px" cellspacing="0px" class="percentgraph"><tr class="percentgraph"><td align="right" class="percentgraph" width="40">100%</td><td class="percentgraph"><div class="percentgraph"><div class="greenbar" style="width:100px"><span class="text">2/2</span></div></div></td></tr></table></td><td><table cellpadding="0px" cellspacing="0px" class="percentgraph"><tr class="percentgraph"><td align="right" class="percentgraph" width="40"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">N/A</a></td><td class="percentgraph"><div class="percentgraph"><div class="na" style="width:100px"><span class="text"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">N/A</a></span></div></div></td></tr></table></td><td class="value"><span class="hidden">2.2222222222222223;</span>2.222</td></tr>
  <tr><td><a href="org.dellroad.stuff.graph.TopologicalSorter.html">TopologicalSorter$EdgeLister</a></td><td><table cellpadding="0px" cellspacing="0px" class="percentgraph"><tr class="percentgraph"><td align="right" class="percentgraph" width="40"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">N/A</a></td><td class="percentgraph"><div class="percentgraph"><div class="na" style="width:100px"><span class="text"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">N/A</a></span></div></div></td></tr></table></td><td><table cellpadding="0px" cellspacing="0px" class="percentgraph"><tr class="percentgraph"><td align="right" class="percentgraph" width="40"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">N/A</a></td><td class="percentgraph"><div class="percentgraph"><div class="na" style="width:100px"><span class="text"><a class="dfn" href="help.html" onclick="popupwindow('help.html'); return false;">N/A</a></span></div></div></td></tr></table></td><td class="value"><span class="hidden">2.2222222222222223;</span>2.222</td></tr>

</table>
<div class="separator">&nbsp;</div>
<table cellspacing="0" cellpadding="0" class="src">
<tr>  <td class="numLine">&nbsp;1</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;2</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">/*</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;3</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment"> * Copyright (C) 2008-2009 Archie L. Cobbs. All rights reserved.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;4</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment"> *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;5</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment"> * $Id: org.dellroad.stuff.graph.TopologicalSorter.html 101 2011-05-10 16:43:38Z archie.cobbs $</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;6</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment"> */</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;7</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;8</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">package</span> org.dellroad.stuff.graph;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;9</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;10</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">import</span> java.util.ArrayList;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;11</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">import</span> java.util.Collection;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;12</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">import</span> java.util.Collections;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;13</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">import</span> java.util.Comparator;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;14</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">import</span> java.util.HashMap;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;15</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">import</span> java.util.List;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;16</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">import</span> java.util.Set;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;17</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;18</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">/**</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;19</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment"> * Topological sorting utility class.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;20</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment"> */</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;21</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="keyword">public</span> <span class="keyword">class</span> TopologicalSorter&lt;E&gt; {</pre></td></tr>
<tr>  <td class="numLine">&nbsp;22</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;23</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> <span class="keyword">final</span> Collection&lt;E&gt; nodes;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;24</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> <span class="keyword">final</span> EdgeLister&lt;E&gt; edgeLister;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;25</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> <span class="keyword">final</span> Comparator&lt;? <span class="keyword">super</span> E&gt; tieBreaker;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;26</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;27</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> HashMap&lt;E, Boolean&gt; visited;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;28</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> ArrayList&lt;E&gt; ordering;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;29</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;30</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="comment">/**</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;31</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * Primary constructor.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;32</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;33</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * @param nodes partially ordered nodes to be sorted</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;34</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * @param edgeLister provides the edges defining the partial order</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;35</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * @param tieBreaker used to sort nodes that are not otherwise ordered,</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;36</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *  or null to tie break based on the original ordering</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;37</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     */</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;38</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;    <span class="keyword">public</span> TopologicalSorter(Collection&lt;E&gt; nodes, EdgeLister&lt;E&gt; edgeLister, Comparator&lt;? <span class="keyword">super</span> E&gt; tieBreaker) {</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;39</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.nodes = nodes;</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;40</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.edgeLister = edgeLister;</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;41</td>  <td class="nbHitsCovered"><a title="Line 41: Conditional coverage 100% (2/2).">&nbsp;29</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 41: Conditional coverage 100% (2/2).">        <span class="keyword">if</span> (tieBreaker == <span class="keyword">null</span>)</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;42</td>  <td class="nbHitsCovered">&nbsp;13</td>  <td class="src"><pre class="src">&nbsp;            tieBreaker = getDefaultTieBreaker();</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;43</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.tieBreaker = tieBreaker;</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;44</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;    }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;45</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;46</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="comment">/**</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;47</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * Convenience constructor for when ties should be broken based on the original ordering.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;48</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;49</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;50</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * Equivalent to:</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;51</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *  &lt;blockquote&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;52</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *  {@code TopologicalSorter(nodes, edgeLister, null);}</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;53</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *  &lt;/blockquote&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;54</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;/p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;55</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     */</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;56</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">public</span> TopologicalSorter(Collection&lt;E&gt; nodes, EdgeLister&lt;E&gt; edgeLister) {</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;57</td>  <td class="nbHitsUncovered">&nbsp;0</td>  <td class="src"><pre class="src"><span class="srcUncovered">&nbsp;        <span class="keyword">this</span>(nodes, edgeLister, <span class="keyword">null</span>);</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;58</td>  <td class="nbHitsUncovered">&nbsp;0</td>  <td class="src"><pre class="src"><span class="srcUncovered">&nbsp;    }</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;59</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;60</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="comment">/**</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;61</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * Produce a total ordering of the nodes consistent with the partial ordering</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;62</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * implied by the edge lister and tie breaker provided to the constructor.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;63</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;64</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;65</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * The returned list will have the property that if there is an edge from X to Y,</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;66</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * then X will appear before Y in the list. If there is no edge (or sequence of edges) from X to Y</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;67</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * in either direction, then X will appear before Y if the tie breaker sorts X before Y.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;68</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;/p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;69</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;70</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;71</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * This implementation runs in linear time in the number of nodes in the graph.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;72</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;/p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;73</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;74</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * @throws IllegalArgumentException if the partial ordering relation contains a cycle</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;75</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     */</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;76</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">public</span> List&lt;E&gt; sort() {</pre></td></tr>
<tr>  <td class="numLine">&nbsp;77</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;78</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Order nodes according to reverse tie breaker ordering</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;79</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        ArrayList&lt;E&gt; startList = Collections.list(Collections.enumeration(<span class="keyword">this</span>.nodes));</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;80</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        Collections.sort(startList, getTieBreaker(<span class="keyword">true</span>));</pre></td></tr>
<tr>  <td class="numLine">&nbsp;81</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;82</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Perform depth-first search through nodes</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;83</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.visited = <span class="keyword">new</span> HashMap&lt;E, Boolean&gt;(startList.size());</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;84</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.ordering = <span class="keyword">new</span> ArrayList&lt;E&gt;(startList.size());</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;85</td>  <td class="nbHitsCovered"><a title="Line 85: Conditional coverage 100% (2/2).">&nbsp;29</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 85: Conditional coverage 100% (2/2).">        <span class="keyword">for</span> (E node : startList)</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;86</td>  <td class="nbHitsCovered">&nbsp;142</td>  <td class="src"><pre class="src">&nbsp;            visit(node, <span class="keyword">true</span>);</pre></td></tr>
<tr>  <td class="numLine">&nbsp;87</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;88</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Reverse list</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;89</td>  <td class="nbHitsCovered">&nbsp;26</td>  <td class="src"><pre class="src">&nbsp;        Collections.reverse(<span class="keyword">this</span>.ordering);</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;90</td>  <td class="nbHitsCovered">&nbsp;26</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">return</span> <span class="keyword">this</span>.ordering;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;91</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;92</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;93</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="comment">/**</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;94</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * Same as {@link #sort sort()} but treats all edges as reversed.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;95</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;96</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;97</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * The returned list will have the property that if there is an edge from X to Y,</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;98</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * then Y will appear before X in the list. If there is no edge (or sequence of edges) from X to Y</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;99</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * in either direction, then X will appear before Y if the tie breaker sorts X before Y.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;100</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * &lt;/p&gt;</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;101</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     *</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;102</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * @throws IllegalArgumentException if the partial ordering relation contains a cycle</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;103</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     */</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;104</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">public</span> List&lt;E&gt; sortEdgesReversed() {</pre></td></tr>
<tr>  <td class="numLine">&nbsp;105</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;106</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Order nodes according to normal tie breaker ordering</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;107</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        ArrayList&lt;E&gt; startList = Collections.list(Collections.enumeration(<span class="keyword">this</span>.nodes));</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;108</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        Collections.sort(startList, getTieBreaker(<span class="keyword">false</span>));</pre></td></tr>
<tr>  <td class="numLine">&nbsp;109</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;110</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Perform depth-first search through nodes</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;111</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.visited = <span class="keyword">new</span> HashMap&lt;E, Boolean&gt;(startList.size());</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;112</td>  <td class="nbHitsCovered">&nbsp;29</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.ordering = <span class="keyword">new</span> ArrayList&lt;E&gt;(startList.size());</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;113</td>  <td class="nbHitsCovered"><a title="Line 113: Conditional coverage 100% (2/2).">&nbsp;29</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 113: Conditional coverage 100% (2/2).">        <span class="keyword">for</span> (E node : startList)</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;114</td>  <td class="nbHitsCovered">&nbsp;141</td>  <td class="src"><pre class="src">&nbsp;            visit(node, <span class="keyword">false</span>);</pre></td></tr>
<tr>  <td class="numLine">&nbsp;115</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;116</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Done</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;117</td>  <td class="nbHitsCovered">&nbsp;26</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">return</span> <span class="keyword">this</span>.ordering;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;118</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;119</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;120</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> <span class="keyword">void</span> visit(E node, <span class="keyword">boolean</span> reverse) {</pre></td></tr>
<tr>  <td class="numLine">&nbsp;121</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;122</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Have we been here before?</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;123</td>  <td class="nbHitsCovered">&nbsp;459</td>  <td class="src"><pre class="src">&nbsp;        Boolean state = <span class="keyword">this</span>.visited.get(node);</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;124</td>  <td class="nbHitsCovered"><a title="Line 124: Conditional coverage 100% (2/2).">&nbsp;459</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 124: Conditional coverage 100% (2/2).">        <span class="keyword">if</span> (state != <span class="keyword">null</span>) {</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;125</td>  <td class="nbHitsCovered"><a title="Line 125: Conditional coverage 100% (2/2).">&nbsp;172</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 125: Conditional coverage 100% (2/2).">            <span class="keyword">if</span> (!state.booleanValue())</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;126</td>  <td class="nbHitsCovered">&nbsp;6</td>  <td class="src"><pre class="src">&nbsp;                <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"cycle in graph containing "</span> + node);</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;127</td>  <td class="nbHitsCovered">&nbsp;166</td>  <td class="src"><pre class="src">&nbsp;            <span class="keyword">return</span>;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;128</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        }</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;129</td>  <td class="nbHitsCovered">&nbsp;287</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.visited.put(node, <span class="keyword">false</span>);</pre></td></tr>
<tr>  <td class="numLine">&nbsp;130</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;131</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Get all destination nodes of all out-edges</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;132</td>  <td class="nbHitsCovered">&nbsp;287</td>  <td class="src"><pre class="src">&nbsp;        ArrayList&lt;E&gt; targets = Collections.list(Collections.enumeration(<span class="keyword">this</span>.edgeLister.getOutEdges(node)));</pre></td></tr>
<tr>  <td class="numLine">&nbsp;133</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;134</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Sort them in reverse desired order and recurse</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;135</td>  <td class="nbHitsCovered">&nbsp;287</td>  <td class="src"><pre class="src">&nbsp;        Collections.sort(targets, getTieBreaker(reverse));</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;136</td>  <td class="nbHitsCovered"><a title="Line 136: Conditional coverage 100% (2/2).">&nbsp;287</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 136: Conditional coverage 100% (2/2).">        <span class="keyword">for</span> (E target : targets)</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;137</td>  <td class="nbHitsCovered">&nbsp;176</td>  <td class="src"><pre class="src">&nbsp;            visit(target, reverse);</pre></td></tr>
<tr>  <td class="numLine">&nbsp;138</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;139</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">// Add this node to list in post-order and mark complete</span></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;140</td>  <td class="nbHitsCovered">&nbsp;277</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.ordering.add(node);</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;141</td>  <td class="nbHitsCovered">&nbsp;277</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">this</span>.visited.put(node, <span class="keyword">true</span>);</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;142</td>  <td class="nbHitsCovered">&nbsp;277</td>  <td class="src"><pre class="src">&nbsp;    }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;143</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;144</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> Comparator&lt;? <span class="keyword">super</span> E&gt; getDefaultTieBreaker() {</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;145</td>  <td class="nbHitsCovered">&nbsp;13</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">final</span> HashMap&lt;E, Integer&gt; orderMap = <span class="keyword">new</span> HashMap&lt;E, Integer&gt;(<span class="keyword">this</span>.nodes.size());</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;146</td>  <td class="nbHitsCovered">&nbsp;13</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">int</span> posn = 0;</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;147</td>  <td class="nbHitsCovered"><a title="Line 147: Conditional coverage 100% (2/2).">&nbsp;13</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 147: Conditional coverage 100% (2/2).">        <span class="keyword">for</span> (E node : <span class="keyword">this</span>.nodes)</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;148</td>  <td class="nbHitsCovered">&nbsp;58</td>  <td class="src"><pre class="src">&nbsp;            orderMap.put(node, posn++);</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;149</td>  <td class="nbHitsCovered">&nbsp;13</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">return</span> <span class="keyword">new</span> Comparator&lt;E&gt;() {</pre></td></tr>
<tr>  <td class="numLine">&nbsp;150</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;            <span class="keyword">public</span> <span class="keyword">int</span> compare(E node1, E node2) {</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;151</td>  <td class="nbHitsCovered">&nbsp;193</td>  <td class="src"><pre class="src">&nbsp;                <span class="keyword">return</span> orderMap.get(node1) - orderMap.get(node2);</pre></td></tr>
<tr>  <td class="numLine">&nbsp;152</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;            }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;153</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        };</pre></td></tr>
<tr>  <td class="numLine">&nbsp;154</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;155</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;156</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">private</span> Comparator&lt;? <span class="keyword">super</span> E&gt; getTieBreaker(<span class="keyword">boolean</span> reverse) {</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;157</td>  <td class="nbHitsCovered"><a title="Line 157: Conditional coverage 100% (2/2).">&nbsp;345</a></td>  <td class="src"><pre class="src">&nbsp;<a title="Line 157: Conditional coverage 100% (2/2).">        <span class="keyword">if</span> (reverse)</a></pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;158</td>  <td class="nbHitsCovered">&nbsp;173</td>  <td class="src"><pre class="src">&nbsp;            <span class="keyword">return</span> Collections.reverseOrder(<span class="keyword">this</span>.tieBreaker);</pre></td></tr>
<tr>  <td class="numLineCover">&nbsp;159</td>  <td class="nbHitsCovered">&nbsp;172</td>  <td class="src"><pre class="src">&nbsp;        <span class="keyword">return</span> <span class="keyword">this</span>.tieBreaker;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;160</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;161</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;162</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="comment">/**</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;163</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     * Implemented by classes that can enumerate the outgoing edges from a node in a graph.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;164</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">     */</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;165</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">interface</span> EdgeLister&lt;E&gt; {</pre></td></tr>
<tr>  <td class="numLine">&nbsp;166</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
<tr>  <td class="numLine">&nbsp;167</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        <span class="comment">/**</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;168</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">         * Get the set of all nodes X for which there is an edge from {@code node} to X.</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;169</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;<span class="comment">         */</span></pre></td></tr>
<tr>  <td class="numLine">&nbsp;170</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;        Set&lt;E&gt; getOutEdges(E node);</pre></td></tr>
<tr>  <td class="numLine">&nbsp;171</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;    }</pre></td></tr>
<tr>  <td class="numLine">&nbsp;172</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;}</pre></td></tr>
<tr>  <td class="numLine">&nbsp;173</td>  <td class="nbHits">&nbsp;</td>
  <td class="src"><pre class="src">&nbsp;</pre></td></tr>
</table>

<div class="footer">Report generated by <a href="http://cobertura.sourceforge.net/" target="_top">Cobertura</a> 1.9.4.1 on 5/10/11 11:43 AM.</div>
</body>
</html>
